﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//46. 全排列
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Sol46
{


    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> Permute(int[] nums)
    {
       
       

      
        IList<int> path = new List<int>();
        bool[] used = new bool[nums.Length];//记录是否使用过，不需要用map，数组够用而且快

        //初始化是false
        //for (int i = 0; i < nums.Length; i++)
        //{
        //    Console.WriteLine(used[i]);
        //}
        DFS(nums, path,used);

        return res;
    }

    private void DFS(int[] nums, IList<int> path, bool[] used)
    {
        //什么时候收集
        if (path.Count == nums.Length)
        {

            res.Add(new List<int>(path));
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {

            //if(i== curindex)
            //{
            //    continue;//这样只能跳过一个，但是应该记录所有的
            //}

            if (!used[i])
            {
                path.Add(nums[i]);//不可以重复
                used[i] = true;
                DFS(nums, path, used);
                path.RemoveAt(path.Count - 1);
                used[i] = false;
            }
            

        }
    }
}

class Program46
{
    static void Main46(string[] args)
    {

        int[] nums = { 1, 2, 3};
        Sol46 sol = new Sol46();
        IList<IList<int>> res = sol.Permute(nums);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }

    }
}
